#ifndef __TREES_H__
#define __TREES_H__

#include <limits.h>
#include <list>

//#define TREE_DEBUG

using namespace std;

namespace Trees
{
	class IllegalTreeOperationException {};
	class UnsupportedTreeOperationException {};
	
	
	template <class E>
	class EdgeInfo
	{
	typedef typename list<EdgeInfo<E> >::iterator EI;
	public:
		EdgeInfo() {}
		EdgeInfo(const E& val) : m_cost(val) {}
		EdgeInfo(const E& val, const EI& itr) : m_cost(val), edgeItr(itr) {}
		
		E m_cost;
		EI edgeItr;
		
		template <class E1>
		friend bool operator>(const EdgeInfo<E1>& ei1, const EdgeInfo<E1>& ei2);
		
		template <class E1>
		friend bool operator<(const EdgeInfo<E1>& ei1, const EdgeInfo<E1>& ei2);

		template <class E1>
		friend bool operator<=(const EdgeInfo<E1>& ei1, const EdgeInfo<E1>& ei2);
	};

	/*********************************************************************
	 *
	 *             H E L P E R     T E M P A T E S 
	 *
	 ********************************************************************/
	template <class X>
	const X sum(const X& a, const X& b);
	
	
	template <class X>
	const X max_value();
	
	template <class X>
	const X min_value();
	
	template <>
	inline const int sum(const int& a, const int& b)
	{
		return a + b;
	}

	template <>
	inline const double sum(const double& a, const double& b)
	{
		return a + b;
	}

	template <>
	inline const int max_value()
	{
		return INT_MAX;
	}

	template <>
	inline const int min_value()
	{
		return INT_MIN;
	}
	
	template <>
	inline const EdgeInfo<int> max_value()
	{
		EdgeInfo<int> ei;
		ei.m_cost = max_value<int>();
		ei.edgeItr = 0;
		return ei;
	}
	
	template <>
	inline const EdgeInfo<int> sum(const EdgeInfo<int>& a, const EdgeInfo<int>& b)
	{
		return EdgeInfo<int>(a.m_cost + b.m_cost, a.edgeItr);
	}

	template <class E>
	inline bool operator<(const EdgeInfo<E>& ei1, const EdgeInfo<E>& ei2)
	{
		return ei1.m_cost < ei2.m_cost;
	}

	template <class E>
	inline bool operator>(const EdgeInfo<E>& ei1, const EdgeInfo<E>& ei2)
	{
		return ei1.m_cost > ei2.m_cost;
	}

	template <class E>
	inline bool operator<=(const EdgeInfo<E>& ei1, const EdgeInfo<E>& ei2)
	{
		return ei1.m_cost <= ei2.m_cost;
	}
}

#endif
